#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
bool comVec(vector<int> &a, vector<int> &b)
{
    return a[0] < b[0];
}
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        if (intervals.size() == 0)
            return intervals;

        sort(intervals.begin(), intervals.end(), comVec);
        vector<vector<int>> ans;
        // 使用一个快慢双指针进行历遍
        int slow = 0;
        int fast;
        while(slow < intervals.size()){
            // 先取出第一个区间
            int fbegin = intervals[slow][0];
            int fend = intervals[slow][1];
            // 取下一个区间
            fast = slow + 1;
            // 首选判断是否存在下一个区间，若不存在则记得把上一个区间放到答案中
            if(fast >= intervals.size()){
                ans.push_back(vector<int>{fbegin,fend});
            } else {
            // 存在下一个区间
                int sbegin = intervals[fast][0];
                int send = intervals[fast][1];
                
                // 合并
                while(sbegin <= fend){
                    fend = send > fend ? send : fend;
                    fast++;
                    // 记得判断是否越界
                    if(fast >= intervals.size()){
                        break;
                    } else {
                        sbegin = intervals[fast][0];
                        send = intervals[fast][1];
                    }
                }
                ans.push_back(vector<int>{fbegin,fend});
            }
            slow = fast;
        }
        return ans;
    }
};
int main()
{
    Solution solution;
    // vector<vector<int>> nums = {{2,6},{1,3},{8,10},{15,18}};
    vector<vector<int>> nums = {{1,4},{2,3}};
    vector<vector<int>> ans = solution.merge(nums);
    for(auto iter=ans.begin();iter<ans.end();iter++){
        cout<<'['<<(*iter)[0]<<","<<(*iter)[1]<<']'<<endl;
    }
    return 0;
}